package com.cn.algorithm.leetcode.array.two;

/*
*
*238. 除自身以外数组的乘积
中等
相关标签
相关企业
提示
给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。

题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在  32 位 整数范围内。

请 不要使用除法，且在 O(n) 时间复杂度内完成此题。



示例 1:

输入: nums = [1,2,3,4]
输出: [24,12,8,6]
示例 2:

输入: nums = [-1,1,0,-3,3]
输出: [0,0,9,0,0]


提示：

2 <= nums.length <= 105
-30 <= nums[i] <= 30
保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在  32 位 整数范围内


进阶：你可以在 O(1) 的额外空间复杂度内完成这个题目吗？（ 出于对空间复杂度分析的目的，输出数组 不被视为 额外空间。）
*
* */

import java.util.Arrays;

public class ArrayProduct {

    public static void main(String[] args) {
        int[] arr = {1,2,3,4};
        System.out.println(Arrays.toString(productExceptSelf2(arr)));
    }

    public static int[] productExceptSelf2(int[] nums) {
        int[] arr = new int[nums.length];
        arr[0] = 1;
        for (int i = 1; i < nums.length; i++) { //从左向右，每一个都不包含自己,移入arr中
            arr[i] = nums[i - 1] * arr[i - 1];
        }
        int max = 1;
        for (int i = nums.length - 1; i >= 0; i--) {//从右向左，将右边乘积 再乘以左边乘积，即可得出结果
            arr[i] = arr[i] * max;
            max = max * nums[i];
        }
        return arr;
    }


    public static int[] productExceptSelf(int[] nums) {
        int[] arr = new int[nums.length];
        int max = 1;
        boolean hasZero = false;
        int zeroCount = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                max *= nums[i];
            } else {
                if (!hasZero) {
                    hasZero = true;
                }
                zeroCount++;
            }
        }
        for (int i = 0; i < nums.length; i++) {
            arr[i] = hasZero ? zeroCount > 1 ? 0 : nums[i] == 0 ? max : 0 : max / nums[i];
        }
        return arr;
    }
}
